package com.duoduo.链表;

import com.duoduo.ListNode;

import java.util.List;

/**
 * @program: algorithm
 * @description: 重排链表143
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 *
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 输入：head = [1,2,3,4]
 * 输出：[1,4,2,3]
 * 输入：head = [1,2,3,4,5]
 * 输出：[1,5,2,4,3]
 * @author: chaidl  ！
 * @create: 2022-05-17 22:54
 */
public class 重排链表143 {
	/**
	* 1 -> 2 -> 3 -> 4 -> 5 -> 6
	 * 第一步，将链表平均分成两半
	 * 1 -> 2 -> 3
	 * 4 -> 5 -> 6
	 *
	 * 第二步，将第二个链表逆序
	 * 1 -> 2 -> 3
	 * 6 -> 5 -> 4
	 *
	 * 第三步，依次连接两个链表
	 * 1 -> 6 -> 2 -> 5 -> 3 -> 4
	*/
	public void reorderList1(ListNode head) {
		if(head==null || head.next==null || head.next.next == null){
			return;
		}
		// 1 -> 2 -> 3 -> 4 -> 5 -> 6
		ListNode slow=head,fast=head;
		while(fast.next!=null && fast.next.next!=null){
			slow=slow.next;
			fast=fast.next.next;
		}
		ListNode mid=slow.next;
		slow.next=null;
		//反转链表4 -> 5 -> 6 ---> 6 -> 5 -> 4
		ListNode fzNode=reverseList(mid);
		// 合并
		while(fzNode!=null){
			ListNode tmpNode=fzNode.next;
			fzNode.next=head.next;
			head.next=fzNode;
			head=fzNode.next;
			fzNode=tmpNode;
		}
	}
	public ListNode reverseList(ListNode head){
		if (head == null || head.next == null) {
			return head;
		}
		ListNode tmpNode=reverseList(head.next);
		head.next.next=head;
		head.next=null;
		return tmpNode;
	}
	public void reorderList(ListNode head) {
		if (head==null || head.next == null){
			return;
		}
	//	寻找中间链表
		ListNode fast=head;
		ListNode slow=head;
		while (fast.next != null && fast.next.next!=null){
			slow=slow.next;
			fast=fast.next.next;
		}
	//	反转中间链表之后的链表
		ListNode preeMiddle=slow;
		//反转3-4-5-6   3-6-5-4
		ListNode preCurrent=slow.next;
		while (preCurrent.next!=null){
			ListNode tmp = preCurrent.next;
			preCurrent.next=tmp.next;
			tmp.next=preeMiddle.next;
			preeMiddle.next=tmp;
		}
	//	梅花间隔插入
		slow=head;
		fast=preeMiddle.next;
		while (slow!=preeMiddle){
			preeMiddle.next=fast.next;
			fast.next=slow.next;
			slow.next=fast;
			slow=fast.next;
			fast=preeMiddle.next;
		}
	}
}
